package com.java.comprehensive.arithmetic.programmers;

import lombok.val;
import util.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 窦绍飞
 * @Date: 2022/6/7
 */
public class RemoveDuplicateNodes {

	//额外空间
	public static ListNode removeDuplicateNodes(ListNode head) {
		if (head == null) return head;

		List<Integer> ids = new ArrayList<>();
		ids.add(head.val);
		ListNode pre = head;
		while (pre.next != null) {
			ListNode cur = pre.next;
			if (ids.contains(cur.val)) {
				pre.next = pre.next.next;
			} else {
				ids.add(cur.val);
				pre = pre.next;
			}
		}
		pre.next = null;
		return head;
	}

	//双重循环
	public static ListNode removeDuplicateNodes_2(ListNode head) {
		if (head == null) return head;

		ListNode ob = head;

		while (ob != null) {
			ListNode oc = ob;
			while (oc.next != null) {
				if (ob.val == oc.next.val) {
					oc.next = oc.next.next;
				} else {
					oc = oc.next;
				}
			}
			ob = ob.next;
		}
		return head;
	}

	public static void main(String[] args) {
		//[1, 2, 3, 3, 2, 1]
		ListNode _1 = new ListNode();
		ListNode _2 = new ListNode();
		ListNode _3 = new ListNode();
		ListNode _4 = new ListNode();
		ListNode _5 = new ListNode();
		ListNode _6 = new ListNode();
		_1.val = 1;
		_2.val = 2;
		_3.val = 3;
		_4.val = 3;
		_5.val = 2;
		_6.val = 1;
		_1.next = _2;
		_2.next = _3;
		_3.next = _4;
		_4.next = _5;
		_5.next = _6;
		removeDuplicateNodes_2(_1);
		System.out.println(_1);
	}

}
